/**
 * Created With IntelliJ IDEA
 * Description:leetcode:面试题 17.04. 消失的数字
 * https://leetcode.cn/problems/missing-number-lcci/
 * User: DELL
 * Data: 2022-12-02
 * Time: 13:29
 */

class Solution {
    //方法一：运用数学方法求得0~n的总和，之后减去集合中的每一个元素即可得到
    public int missingNumber(int[] nums) {
        int n = nums.length;
        long sum = n * (n + 1) / 2;
        for (int i = 0; i < n; i++) {
            sum -= nums[i];
        }
        return (int)sum;
    }
    //方法二：运用异或的方法，将原数组中异或的结果再跟0~n的每个整数进行一次异或
    public int missingNumber2(int[] nums) {
        int n = nums.length;
        int xor = 0;
        for (int i = 0; i < n; i++) {
            xor ^= nums[i];
            xor ^= i;
        }
        xor ^= n;
        return xor;
    }
    //另外还有运用哈希表的方法，不过不如以上两种方法好
}
